| 翻訳と辞書 |
| Heawood graph ： ウィキペディア英語版 |
Heawood graph
In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.
==Combinatorial properties==
The graph is cubic, and all cycles in the graph have six or more edges. Every smaller cubic graph has shorter cycles, so this graph is the 6-cage, the smallest cubic graph of girth 6. It is a distance-transitive graph (see the Foster census) and therefore distance regular.
There are 24 perfect matchings in the Heawood graph; for each matching, the set of edges not in the matching forms a Hamiltonian cycle. For instance, the figure shows the vertices of the graph placed on a cycle, with the internal diagonals of the cycle forming a matching. By subdividing the cycle edges into two matchings, we can partition the Heawood graph into three perfect matchings (that is, 3-color its edges) in eight different ways.〔 Every two perfect matchings, and every two Hamiltonian cycles, can be transformed into each other by a symmetry of the graph.〔.〕
There are 28 six-vertex cycles in the Heawood graph. Each 6-cycle is disjoint from exactly three other 6-cycles; among these three 6-cycles, each one is the symmetric difference of the other two. The graph with one node per 6-cycle, and one edge for each disjoint pair of 6-cycles, is the Coxeter graph.〔.〕
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Heawood graph」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|